//2009/08/08 13:15:29
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

class HanoiTower
{
public:
    int moves(string pegA, string pegB, string pegC)
    {
        memo.clear();
        queue<string> q;
        q.push(pegA);
        q.push(pegB);
        q.push(pegC);
        bool dbg = 0;
        if (pegB == "C") dbg = 1;
        while (!q.empty())
        {
            string A = POP(q), B = POP(q), C = POP(q);
            long long hValue = HASH(A,B,C);
            long long nhValue;
            if (check(A,B,C)) return memo[hValue];
            string nA, nB, nC;
            if (A.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nA, nB);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
            if (C.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nC, nB);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
            if (A.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nA, nC);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
            if (B.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nB, nC);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
            if (B.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nB, nA);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
            if (C.size() != 0)
            {
                nA = A;
                nB = B;
                nC = C;
                transfer(nC, nA);
                nhValue = HASH(nA, nB, nC);
                if (memo.find(nhValue) == memo.end())
                {
                    q.push(nA);
                    q.push(nB);
                    q.push(nC);
                    memo[nhValue] = 1 + memo[hValue];
                }
            }
        }
        return -1;
    }
private:
    map<long long, int> memo;
    long long HASH(string &s)
    {
        long long ret = 0;
        for (int i=0; i<s.size(); i++)
        {
            ret = ret * 4LL + s[i] - 'A' + 1;
        }
        return ret;
    }
    long long HASH(string &A, string &B, string &C)
    {
        return HASH(A)*1048576LL*HASH(B)*1048576LL*HASH(C)*1048576LL;
    }
    bool check(string &A, string &B, string &C)
    {
        for (int i=0; i<A.size(); i++) if (A[i] != 'A') return false;
        for (int i=0; i<B.size(); i++) if (B[i] != 'B') return false;
        for (int i=0; i<C.size(); i++) if (C[i] != 'C') return false;
        return true;
    }
    void transfer(string &A, string &B)
    {
        B += A[A.size() - 1];
        A.erase(A.begin() + (int) A.size() - 1);
    }
    string POP(queue<string> &q)
    {
        string ret = q.front();
        q.pop();
        return ret;
    }
};
